#include "main/utils.h"
using namespace std;

int partition(vector<int> &nums, int begin, int end) {
  int small = begin - 1;
  for (int i = begin; i < end; ++i) {
    if (nums[i] < nums[end]) {
      ++small;
      swap(nums, small, i);
    }
  }
  ++small;
  swap(nums, small, end);
  return small;
}

int findKthLargest(vector<int> nums, const int& k) {
  int length = nums.size();
  int begin = 0;
  int end = length - 1;
  int privot = partition(nums, 0, end);
  while (privot != length - k) {
    if (privot > length - k) {
      end = privot - 1;
    } else {
      begin = privot + 1;
    }
    privot = partition(nums, begin, end);
  }
  return nums[privot];
}

int main() {
  vector<int> nums = {3, 1, 2, 4, 0, 9, 6};
  cout << findKthLargest(nums, 3) << endl;

  return 0;
}
